package com.hejing.排序算法;

import java.text.SimpleDateFormat;
import java.util.Date;

public class QuickSort {
    public static void main(String[] args) {

        // int[] arr = {1, -1, 90, 31, 922, -102, 0, 221, 441, -100};

        int count = 8000000;
        int[] arr = new int[count];
        for (int i = 0; i < count; i++) {
            arr[i] = (int)(Math.random() * 10000000);
        }


        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:SSS");
        Date date1 = new Date();
        String date1Str = simpleDateFormat.format(date1);
        System.out.println("排序前的时间: " + date1Str);
        // System.out.println("排序前的数组: " + Arrays.toString(arr));

        quickSort(arr, 0, arr.length - 1);

        Date date2 = new Date();
        String date2Str = simpleDateFormat.format(date2);
        System.out.println("排序后的时间:" + date2Str);
        // System.out.println("排序后的数组: " + Arrays.toString(arr));

    }

    /**
     * 冒泡排序的升级版本
     * 8000000级别的数据，耗时约: 700-800毫秒；注,对于8000000级别的数据，希尔排序需要约500ms
     * @param arr  待排序数组
     * @param left 待排序数组的左下标
     * @param right 待排序数组的右下标
     */
    public static void quickSort(int[] arr, int left, int right){
        // 为什么递归结束条件是 left >= right ?
        // 递归结束条件:基准值 左边/右边 的数组不存在(left > right) 或者 数组元素只有一个(left = right)
        // 此时的数组已经是最小原子了，必然是有序的，也便可以结束递归。
        if (left >= right) {
            return;
        }
        int i = left;
        int j = right;
        int temp = arr[left];  // 基准值
        int temp_data = 0;
        while (i < j) {
            // 为什么是右边的哨兵j先开始?
            // 这和我们定的基准值的位置有关，此处我们定的基准值是数组的第一个元素，则当 i= j循环退出之时，必然是
            // i 不动，j移位到i所在的元素上，而此时i位置上的元素是小于基准值的，则后续进行基准值所在位置与i所在位置
            // 交换的时候，仍然满足 基准值左边的数小于基准值，右边的数大于基准值。
            // 容易理解的，如果定的基准值是数组最后一个元素，则必然是哨兵i先移动。
            while (i < j && arr[j] >= temp) j--;
            while (i < j && arr[i] <= temp) i++;
            // 有可能上面的两个循环退出之后，i = j，故而下面的交换操作可以加一个 if判断。
            if (i < j) {
                temp_data = arr[i];
                arr[i] = arr[j];
                arr[j] = temp_data;
            }
        }
        // 循环退出时，必然有:i = j
        arr[left] = arr[j];
        arr[j] = temp;

        // 递归排序基准值左边的数组
        // 递归结束条件: 如果数组为空，则left = j, left > right(j - 1)
        // 递归结束条件: 如果数组元素只有一个，则left = right(j - 1)
        quickSort(arr, left, j - 1);

        // 递归排序基准值右边的数组
        // 递归结束条件: 如果数组为空，则j = right, left(j + 1) > right
        // 递归结束条件: 如果数组元素只有一个，则 left(j + 1) = right
        quickSort(arr, j + 1, right);
    }
}




















